package com.yoshino.leetcode.oneHundred.second;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {

    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode h1 = head, h2 = head.next, h3;
        h1.next = null;
        do {
            h3 = h2.next;
            h2.next = h1;
            h1 = h2;
            h2 = h3;
        } while (h3 != null);
        return h1;
    }

    Map<Node, Node> cache = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = new Node(head.val);
        cache.put(head, cur);
        cur.next = copyRandomList(head.next);
        cur.random = cache.get(head.random);
        return cur;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}